// https://leetcode.cn/problems/find-largest-value-in-each-tree-row/description/

// 算法思路总结：
// 1. 广度优先搜索计算二叉树每层的最大值
// 2. 使用队列辅助进行层序遍历
// 3. 每层遍历时记录当前层的最大值
// 4. 遍历完一层后将最大值加入结果数组
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <queue>
#include <vector>
#include <algorithm>

struct TreeNode 
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

TreeNode* buildTree(const vector<string>& nodes) 
{
    if (nodes.empty() || nodes[0] == "null") return nullptr;
    
    TreeNode* root = new TreeNode(stoi(nodes[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    
    while (!q.empty() && i < nodes.size()) 
    {
        TreeNode* current = q.front();
        q.pop();
        
        if (i < nodes.size() && nodes[i] != "null") 
        {
            current->left = new TreeNode(stoi(nodes[i]));
            q.push(current->left);
        }
        i++;
        
        if (i < nodes.size() && nodes[i] != "null") 
        {
            current->right = new TreeNode(stoi(nodes[i]));
            q.push(current->right);
        }
        i++;
    }
    
    return root;
}

class Solution 
{
public:
    vector<int> largestValues(TreeNode* root) 
    {
        if (root == nullptr) return {};

        queue<TreeNode*> q;
        q.push(root);
        vector<int> ret;

        while (!q.empty())
        {
            int sz = q.size();
            int maxVal = q.front()->val;

            for (int i = 0 ; i < sz ; i++)
            {
                auto front = q.front();
                q.pop();
                maxVal = max(maxVal, front->val);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
            ret.push_back(maxVal);
        }

        return ret;
    }
};

int main()
{
    vector<string> nodes1 = {"1","3","2","5","3","null","9"};
    vector<string> nodes2 = {"1","2","3"};

    Solution sol;

    TreeNode* root1 = buildTree(nodes1);
    TreeNode* root2 = buildTree(nodes2);

    vector<int> result1 = sol.largestValues(root1);
    vector<int> result2 = sol.largestValues(root2);

    cout << "[";
    for (int i = 0 ; i < result1.size() ; i++)
    {
        cout << result1[i];
        if (i < result1.size() - 1) cout << ",";
    }
    cout << "]" << endl;

    cout << "[";
    for (int i = 0 ; i < result2.size() ; i++)
    {
        cout << result2[i];
        if (i < result2.size() - 1) cout << ",";
    }
    cout << "]" << endl;;


    return 0;
}